2621.
Kings Tour
Chess is a game
played on a board of eight rows and eight columns of squares. Columns are
marked ‘a’ to ‘h’ from left to
right, and rows are numbered ‘1’ to ‘8’ from bottom to top. To play chess, you have to understand the paths by
which pieces can attack. One of the pieces is a pawn. A pawn attacks
diagonally, one square upward and to the left or right. For example, if a pawn
is on c3, it threatens d4 and b4. Another piece is the king. A king can move or attack one square
in any direction vertically, horizontally or diagonally. When a pawn or king
attacks a square, it moves to that square and captures the piece occupying that
square.
You are given
the starting positions of a king, pawn A, and pawn B. Find the minimum number
of moves necessary for the king to capture pawn A. The king is not allowed to
move to squares threatened by either of the pawns, and it is not allowed to
move outside of the board. The king can capture pawn B but does not have to.
Neither of the pawns will move.
Input. Consists of
multiple test cases. Each line describes one test case that contains the
starting positions of a king, pawn A and pawn B. Each position contains exactly
two characters. The first character is the column (‘a’ – ‘h’) and the second character is the row (‘1’ – ‘8’). All three
positions will be distinct. The king's starting position will not be threatened
by a pawn.
Output. For each test
case print in a separate line the minimum number of moves necessary for the
king to capture pawn A.
|
Sample
input |
Sample
output |
|
c4 e6 d5 g2 a8 a2 a3 b1 c1 |
2 6 7 |
SOLUTION
graphs – breadth first search
Рассмотрим два
варианта движения короля:
1. Король
направляется к пешке А несмотря на положение пешки В и съедает ее;
2. Король
направляется к пешке В, съедает ее и потом двигается к пешке А.
В обоих случаях
при движении короля используется кратчайший путь, который находится поиском в
ширину. Находим наименьшее количество ходов в первом и во втором случаях и
возвращаем наименьшее среди них значение. Второй случай необходим, например, если изначально пешка А
находится под ударом пешки B.
В поля,
находящиеся под ударом пешек, изначально поставим значения 1000. Таким образом
при поиске в ширину король на них не зайдет. Начальные положения короля и двух
пешек занесем соответственно в переменные (kx,
ky), (pax, pay), (pbx, pby).
Запустим bfs(kx, ky). Занесем в переменные a
и b наименьшее число ходов, которыми
можно добраться до пешки А и В соответственно: a = m[pax][pay], b = m[pbx][pby]. Если пешка В сбивается, то следует
запустить bfs(pbx, pby), найдя таким образом кратчайший
путь от пешки В до А. Добавим к b
значение m[pax][pay] после второго вызова bfs. Таким образом в a содержится длина кратчайшего пути короля до достижения цели без
сбивания пешки В, а в b – со
сбиванием. Вычисляем меньшее значение среди a
и b.
Algorithm realization
Шахматную доску храним
в массиве m. Очередь пар d используется для поиска в ширину и содержит
координаты полей шахматной доски (x, y).
Массивы xx и yy описывают возможные ходы короля: из клетки (i, j)
король может пойти в любую из клеток (i
+ xx[k], j + yy[k]), где 1 ≤
k ≤ 8.
int m[10][10];
deque<pair<int,int> > d;
int xx[8] = {1, 1, 1, -1, -1, -1, 0, 0};
int yy[8] = {-1, 0, 1, -1, 0, 1, 1, -1};
Функция cango
проверяет, не находится ли поле (x, y) за границами шахматной доски.
int cango(int
x, int y)
{
if ((x <
1) || (x > 8) || (y < 1) || (y > 8) || (m[x][y] >= 0))
return
0;
return 1;
}
Функция bfs реализует поиск в ширину из клетки (x, y). С ее помощью ищем
кратчайший путь короля до каждой из пешек.
void bfs(int
x, int y)
{
m[x][y] = 0;
d.push_back(make_pair(x,y));
while(!d.empty())
{
pair<int,int> temp = d[0]; d.pop_front();
Перебираем все возможные ходы короля.
for(int i = 0; i < 8; i++)
{
int dx = temp.first + xx[i];
int dy = temp.second + yy[i];
if (cango(dx, dy))
{
m[dx][dy] = m[temp.first][temp.second]
+ 1;
d.push_back(make_pair(dx, dy));
}
}
}
}
Функция attackPawns возвращает наименьшее
количество ходов, за которое король сможет побить пешку A.
int attackPawns(void)
{
memset(m,-1,sizeof(m));
В поля, находящиеся под ударом пешек, поставим значения 1000.
Это делается для того, чтобы при поиске в ширину король в них не зашел.
m[pax-1][pay+1] = m[pax+1][pay+1] = 1000;
m[pbx-1][pby+1] = m[pbx+1][pby+1] = 1000;
bfs(kx,ky);
До пешки А король может добраться
минимум за а ходов, а до пешки B за b ходов.
int a =
m[pax][pay], b = m[pbx][pby];
memset(m,-1,sizeof(m));
m[pax-1][pay+1] = m[pax+1][pay+1] = 1000;
Вычисляем кратчайший путь от пешки В
до пешки А.
bfs(pbx,pby); b += m[pax][pay];
В переменной a содержится
длина кратчайшего пути короля до пешки A без сбивания пешки В, а в переменной b с ее сбиванием. Возвращаем меньшее
значение среди a и b.
return (a
< b) ? a : b;
}
Основная часть программы. Читаем
входные данные. Находим и выводим ответ.
while(scanf("%c%c
%c%c %c%c\n",&kx, &ky, &pax, &pay, &pbx,
&pby) == 6)
{
kx -= 'a' -
1; ky -= '1' - 1; pax -= 'a' - 1; pay -= '1'
- 1;
pbx -= 'a'
- 1; pby -= '1' - 1;
res = attackPawns();
printf("%d\n",res);
}